package example2;

import java.util.HashMap;
import java.util.Map;

//136. 只出现一次的数字
public class LeetCode136 {
    public static void main(String[] args) {

    }
}

/**
 * 方法二：异或运算
 * ^ 是异或运算符，任何数和0异或，结果还是它本身，任何数和它本身异或，结果是0，而且异或满足交换律
 * 所以可以通过异或的方式，对所有的数进行异或，最终两次出现的数都会异或为0，结果就是出现一次的数。
 * 时间复杂度 O(n)       空间  O(1)
 */
class Solution136_2 {
    public int singleNumber(int[] nums) {
        int num = 0;
        for(int i=0;i<nums.length;i++){
            num ^= nums[i];
        }
        return num;
    }
}

/**
 * 方法一：hash
 */
class Solution136_1 {
    public int singleNumber(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<nums.length;i++){
            Integer count = map.get(nums[i]);
            if(count == null){
                count = 0;
            }
            count++;
            map.put(nums[i],count);
        }
        for (Map.Entry<Integer,Integer> entry : map.entrySet()){
            if(entry.getValue() == 1)   return entry.getKey();
        }
        return 0;
    }
}
